# !/usr/bin/python
# -*- coding: utf-8 -*-

"""
@contact: 微信 1257309054
@file: bubble.py
@time: 2022/7/24 11:57
@author: LDC
"""
import random
import time

'''
1、冒泡排序
基本思想：比较相邻的元素大小，将小的前移，大的后移，就像水中的气泡一样，最小的元素经过几次移动，会最终浮到水面上。
原地排序，不需要返回值。
举例：
[22,3,1,6,7,8,2,5]
普通冒泡排序
思路：
第一趟排序 从下标0开始，取出对应的值22
22和3比较，22 > 3 ,22和3交换，
交换后，22和1比较，22 > 1,22和1比较，
最后22会排到最后,
第一趟排序后列表变成
[3,1,6,7,8,2,5，22]
第二趟排序 从下标1开始，取出对应的值1
3和1比较，3 > 1 , 3和1交换，
以此类推，最后列表变成有序的了
[1,2,3,5,6,7,8,22]

这一整个过程就像一个水泡从低往上冒，
越往后水泡就越大(列表后面的元素会逐渐比前面的大)

'''


def bubble_sort(alist):
    list_len = len(alist)
    for i in range(list_len):
        # 定义一个swapped
        # 如果有元素交换过就置为True
        # 如果没有元素交换过就退出循环

        swapped = False
        for j in range(list_len - 1 - i):
            if alist[j] > alist[j + 1]:
                alist[j], alist[j + 1] = alist[j + 1], alist[j]
                swapped = True
        # 搅拌排序
        # 从后面往前面检索，如果前面比后面的大，就交换
        if swapped:
            swapped = False
            # 由于上面已经有一个元素在最后排好序了，所以这时要减2
            for j in range(list_len - 2 - i, 0, -1):
                if alist[j] < alist[j - 1]:
                    alist[j], alist[j - 1] = alist[j - 1], alist[j]
                    swapped = True
        # 如果没有发生元素交换，就说明列表已经是有序的了
        # 这时可以直接退出循环
        if not swapped:
            return alist


def main():
    print(bubble_sort([22, 3, 1, 6, 7, 8, 2, 5]))
    list1 = [random.randint(1, 999) for i in range(10000)]
    list11 = list1.copy()
    start1 = time.perf_counter()
    bubble_sort(list1)
    end1 = time.perf_counter()
    print("冒泡排序      ", end1 - start1)

    start2 = time.perf_counter()
    list4 = sorted(list11)
    end2 = time.perf_counter()
    print("函数sorted排序", end2 - start2)
    print("排序结果", list1 == list4)


if __name__ == '__main__':
    main()
